#include <bits/stdc++.h>

using namespace std;

// 乘积最大子数组
// 给你一个整数数组 nums
// 请你找出数组中乘积最大的非空连续子数组
// 并返回该子数组所对应的乘积
// 测试链接 : https://leetcode.cn/problems/maximum-product-subarray/

class Solution 
{
public:
    int maxProduct(vector<int>& nums) 
    {
        // 本方法对于double类型的数组求最大累乘积也同样适用
        int n = nums.size(), ans = nums[0];
        for(int i = 1, mn = nums[0], mx = nums[0], curmin, curmax; i < n; ++i)
        {
            // curmin : 以 num[i] 结尾的乘积最小的子数组
            // curmax : 以 num[i] 结尾的乘积最大的子数组
            // mn : 以 num[i - 1] 结尾的乘积最大的子数组
            // mx : 以 num[i - 1] 结尾的乘积最大的子数组
            // ans : 整个数组中乘积最大的子数组
            curmin = min(nums[i], min(mn * nums[i], mx * nums[i]));
            curmax = max(nums[i], max(mn * nums[i], mx * nums[i]));
            mn = curmin, mx = curmax;
            ans = max(ans, mx);
        }
        return ans;
    }
};


class Solution 
{
public:
    int maxProduct(vector<int>& nums) 
    {
        // 本方法对于double类型的数组求最大累乘积也同样适用
        int n = nums.size();
        long ret = nums[0];
        long f[n], g[n];
        f[0] = nums[0], g[0] = nums[0];
        for(int i = 1; i < n; ++i)
        {
            long x = nums[i], y = x * f[i - 1], z = x * g[i - 1];
            f[i] = max(x, max(y, z));
            g[i] = min(x, min(y, z));
            ret = max(ret, f[i]);
        }
        return ret;
    }
};